package algorithm;

import java.util.ArrayList;
import java.util.List;

public class leetcode_0051 {
    public static void main(String[] args) {
        System.out.println(solveNQueens(4));
    }
    public static List<List<String>> solveNQueens(int n) {
        List<List<String>> list=new ArrayList<>();
        List<String> path=new ArrayList<>();
        boolean[] lie=new boolean[n];
        boolean[] dia1=new boolean[2*n];
        boolean[] dia2=new boolean[2*n];
        int hang=0;
        dfs(list,path,lie,dia1,dia2,hang,n);
        return list;
    }
    public static void dfs(List<List<String>> list,List<String> path,boolean[] lie,boolean[] dia1,boolean[] dia2,
                 int hang,int n   ){
        if(hang==n){
            list.add(new ArrayList<>(path));
            return;
        }
        for(int i=0;i<n;++i){
            if((!lie[i])&&(!dia1[hang-i+n])&&(!dia2[hang+i])){
                dia1[hang-i+n]=true;
                dia2[hang+i]=true;
                lie[i]=true;
                String s="";
                for(int j=0;j<i;++j){
                    s+=".";
                }
                s+="Q";
                for(int j=i+1;j<n;++j){
                    s+=".";
                }
                path.add(s);
                dfs(list,path,lie,dia1,dia2,hang+1,n);
                dia1[hang-i+n]=false;
                dia2[hang+i]=false;
                lie[i]=false;
                path.remove(path.size()-1);
            }
        }


    }
}
